package day03;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/3 15:39
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一棵 N 叉树的根节点 root ，计算这棵树的直径长度。
 * <p>
 * N 叉树的直径指的是树中任意两个节点间路径中 最长 路径的长度。这条路径可能经过根节点，也可能不经过根节点。
 * <p>
 * （N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔）
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：root = [1,null,3,2,4,null,5,6]
 * 输出：3
 * 解释：直径如图中红线所示。
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入：root = [1,null,2,null,3,4,null,5,null,6]
 * 输出：4
 * 示例 3：
 * <p>
 * <p>
 * <p>
 * 输入: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 * 输出: 7
 */

class Node {
    public int val;
    public List<Node> children;


    public Node() {
        children = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};

public class Solution4 {
    int res = 0;
    public int diameter(Node root) {
        dfs(root);
        return res;
    }

    private int dfs(Node node) {
        if (node == null) {
            return 0;
        }
        int max = 0;
        int secondMax = 0;
        for (Node child : node.children) {
            int temp = dfs(child);
            if (temp > max) {
                secondMax = max;
                max = temp;
            } else if (temp > secondMax) {
                secondMax = temp;
            }
        }
        res = Math.max(max + secondMax, res);
        return 1 + max;
    }
}
